|
The Baillie–PSW primality test is a probabilistic primality testing algorithm that determines if a number is composite or a probable prime. It is named after Robert Baillie, Carl Pomerance, John Selfridge, and Samuel Wagstaff. The Baillie-PSW test is a combination of a strong Fermat probable prime test to base 2 and a strong Lucas probable prime test. The Fermat and Lucas test each has its own list of pseudoprimes, that is, ''composite'' numbers that pass the primality test. For example, the first ten strong pseudoprimes to base 2 are : 2047, 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141, and 52633 . The first ten strong Lucas pseudoprimes (with Lucas parameters ''P'' = 1, ''Q'' = -1) are : 5459, 5777, 10877, 16109, 18971, 22499, 24569, 25199, 40309, and 58519 . The power of the Baillie-PSW test comes from the fact that these lists of strong Fermat pseudoprimes and strong Lucas pseudoprimes have ''no known'' overlap. There is even evidence that the numbers in these lists tend to be ''different kinds'' of numbers. For example, pseudoprimes base 2 tend to fall into the residue class 1 (mod ''m'') for many small ''m'', whereas Lucas pseudoprimes tend to fall into the residue class −1 (mod ''m''). As a result, a number that passes both a strong Fermat and a strong Lucas test is very likely to be prime. No composite number below 264 (approximately 1.845·1019) passes the Baillie-PSW test.〔(【引用サイトリンク】url=http://www.trnicely.net/misc/bpsw.html )〕 Consequently, this can be considered a deterministic primality test on numbers below that bound. There are also no ''known'' composite numbers above that bound that pass the test. In 1980 the authors Pomerance, Selfridge, and Wagstaff offered $30 for the discovery of a counterexample, that is, a composite number that passed this test. Richard Guy incorrectly stated that the value of this prize had been raised to $620, but he was confusing the Lucas sequence with the Fibonacci sequence, and his remarks really apply only to a Conjecture of Selfridge's.〔Guy, R. (1994). "Pseudoprimes. Euler Pseudoprimes. Strong Pseudoprimes." §A12 in ''Unsolved Problems in Number Theory''. 2nd ed., p. 28, New York: Springer-Verlag. ISBN 0-387-20860-7.〕 As of June 2014 the prize remains unclaimed. However, a heuristic argument by Pomerance suggests that there are infinitely many counterexamples. Moreover, Chen and Greene 〔(Baillie-PSW ) John R. Greene's website.〕 have constructed a set ''S'' of 1248 primes such that, among the nearly 21248 products of distinct primes in ''S'', there ''may'' be about 740 counterexamples. However, they are talking about a weaker Baillie-PSW test that substitutes a Fibonacci test for the Lucas one. ==The test== Let ''n'' be the odd positive integer that we wish to test for primality. # Optionally, perform trial division to check if ''n'' is divisible by a small prime number less than some convenient limit. # Perform a base 2 strong probable prime test. If ''n'' is not a strong probable prime base 2, then ''n'' is composite; quit. # Find the first ''D'' in the sequence 5, -7, 9, -11, 13, -15, ... for which the Jacobi symbol (''D''/''n'') is −1. Set ''P'' = 1 and ''Q'' = (1 - ''D'') / 4. # Perform a strong Lucas probable prime test on ''n'' using parameters ''D'', ''P'', and ''Q''. If ''n'' is not a strong Lucas probable prime, then ''n'' is composite. Otherwise, ''n'' is almost certainly prime. Remarks. # The first step is for efficiency only. The Baillie-PSW test works without this step, but if ''n'' has small prime factors, then the quickest way to show that ''n'' is composite is to find a factor by trial division. # The second step is a single application of the Miller-Rabin primality test. There is nothing special about using base 2; other bases might work just as well. However, much work has been done (see above) to verify that the combination of the base 2 strong probable prime test and a strong Lucas test does a good job of distinguishing primes from composites. # Baillie and Wagstaff proved in Theorem 9 on page 1413 of 〔 that the average number of ''D''s that must be tried is about 3.147755149. # If ''n'' is a perfect square, then step 3 will never yield a ''D'' with (''D''/''n'') = −1; this is not a problem because perfect squares are easy to detect using Newton's method for square roots. If step 3 fails to produce a ''D'' quickly, one should check whether ''n'' is a perfect square. # Given ''n'', there are other methods for choosing ''D'', ''P'', and ''Q''. What is important is that the Jacobi symbol (''D''/''n'') be −1. Bressoud and Wagon explain why we want the Jacobi symbol to be −1, as well as why one gets more powerful primality tests if ''Q'' ≠ ± 1.〔 〕 # If ''Q'' ≠ ±1, there are additional tests that can be performed at almost no extra computational cost. After one has computed the powers of ''Q'' and the terms in the Lucas sequences that are used in the strong Lucas probable prime test, these additional primality conditions provide further opportunities to show that ''n'' is composite; see Section 6 of.〔 # There are weaker versions of the Baillie-PSW test, and this one is sometimes referred to as the ''Strong'' Baillie-PSW test. # If the Lucas test is replaced by a Fibonacci test, then it shouldn't be called a Baillie-PSW test, but rather a Selfridge test or a PSW test. See Selfridge's Conjecture on Primality Testing. # Pomerance, Selfridge and Wagstaff offered $30 in 1980 for a composite number passing a weaker version of the Baillie-PSW test. Such a number passing the (strong) Baillie-PSW test would qualify.〔 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Baillie–PSW primality test」の詳細全文を読む スポンサード リンク
|